const int n = 2;
struct Matrix {
	int a[n][n];
	Matrix() {
		this->clear();
	}
	void clear() {
		memset(a, 0, sizeof(a));
	}
	void setOne() {
		this->clear();
		for (int i = 0; i < n; ++ i) {
			a[i][i] = 1;
		}
	}
};

Matrix operator *(const Matrix& x, const Matrix& y) {
	Matrix c;
	for (int k = 0; k < n; ++ k) {
		for (int i = 0; i < n; ++ i) {
			for (int j = 0; j < n; ++ j) {
				c.a[i][j] = (c.a[i][j] + (long long)x.a[i][k] * y.a[k][j])% mod;
			}
		}
	}
	return c;
}

void operator =(Matrix& x, const Matrix& y) {
	memcpy(x.a, y.a, sizeof(x.a));
}

void fibn(int n) {
	Matrix a, s;
	a.a[0][0] = a.a[0][1] = a.a[1][0]  = 1;
	s.setOne();
	for (; n; n >>= 1) {
		if (n & 1) {
			s = s * a;
		}
		a = a * a;
	}
	// s = a ^ n;
	return (s.a[0][0] + s.a[0][1])% mod
}



